| 数据结构 第三章栈和队列 第一节 | 您所在的位置：网站首页 › typedef elemtype › 数据结构 第三章栈和队列 第一节 |
数据结构 第三章栈和队列 第一节
|
开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第7天，点击查看活动详情 数据结构 第三章第一节 栈和队列的定义及特点 栈 定义: 栈是一个 特殊 的线性表，是只能在一端(通常是表尾)进行删除和插入操作的线性表。 也叫 后进先出(Last In First Out) 的线性表，简称 LIFO 结构。例如:碗的堆放，先放的在最下面，后放的在最上面，要取的时候，就只能从最上面的取 相关概念 表尾称为栈顶(Top)\color{red}{栈顶(Top)}栈顶(Top)； 表头称为栈底(Base)\color{red}{栈底(Base)}栈底(Base); 插入元素到栈顶的操作叫做入栈\color{red}{入栈}入栈(也可以叫做压栈(push))。 从栈顶删除一个元素的的操作叫做出栈\color{red}{出栈}出栈(也可以叫做弹栈(pop))。用图形表示如图:
队列 定义: 队列是一种 先进先出(First In First Out----FIFO) 的特殊线性表。 在表一端的插入(表尾)，另一端删除(表头)。例如排队就是一种队列的表示,后来的排在队尾,先来的到头部 由于队列和栈类似，不作详细展开 总结: 定义:只能在表的一端进行插入，表的另一端进行删除的线性表; 逻辑结构:和线性表一样，都是一对一(有前驱和后继节点); 存储结构:可使用顺序队和链队;栈和队列案例举例 把十进制159转为八进制。栈的抽象数据类型的类型定义 栈的表示和实现 采用顺序栈实现 概念 空栈:栈顶和栈底在同一个位置(base==top)\color{red}{同一个位置(base==top)}同一个位置(base==top); 栈满:栈顶减去栈底的差值等于栈的大小(top−base==stacksize)\color{red}{等于栈的大小(top-base==stacksize)}等于栈的大小(top−base==stacksize); 对于栈满之后的做法，可以直接返回报错\color{red}{直接返回报错}直接返回报错;，不再添加后续的元素;也可以直接分配更大的空间\color{red}{直接分配更大的空间}直接分配更大的空间，将元素放到新的栈中。 顺序栈的特点简单，方便，但是易溢出。 上溢(overflow):栈已经满了，还要继续压入元素; 下溢(underflow):栈已经空了，还要继续弹出元素; 栈的基本操作 定义一个顺序栈 #define MaxSize 100 typedef struct{ ElemType *base; ElemType *top; int stacksize; }SqStack; 复制代码初始化顺序栈 #include #include #include typedef int ElemType; typedef struct{ ElemType base;//栈底 ElemType top;//栈顶 ElemType *value; ElemType StackSize; }SqStack; void initStack(SqStack *q,ElemType length){ q->value=(SqStack *)malloc(sizeof(SqStack)*length);//初始化顺序栈q大小 q->top=q->base=-1; q->StackSize=length; } 复制代码清空顺序栈 void clearStack(SqStack *q){ if(q->top!=-1){ q->top=q->base; q->StackSize=0; } } 复制代码销毁顺序栈 void destoryStack(SqStack *q){ free(q); q->StackSize=0; q->value=NULL; q->base=q->top=-1; } 复制代码顺序表的入栈 void pushStack(SqStack *q,ElemType e){ printf("当前栈大小:%d",q->top); if(q->top>=q->StackSize-1){ printf("栈空间已满"); }else{ q->value[++q->top]=e; } } 复制代码顺序栈的出栈 void popStack(SqStack *q){ for(;q->top!=q->base;q->top--){ printf("出栈:%d\n",q->value[q->top]); } printf("栈是空的"); } 复制代码 |
【本文地址】
公司简介
联系我们